package com.lanqiao.huffmancode;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class HuffmanCode {

	public static void main(String[] args) {
		//测试压缩文件
		String srcFile = "f://1.bmp";
		String dstFile = "f://dst.zip";
		zipFile(srcFile, dstFile);
		System.out.println("压缩成功！");
		
		
//		//测试解压文件
//		//解压有问题，需要更改
//		String zipFile = "f://dst.zip";
//		String dstFile = "f://src.bmp";
//		unZipFile(zipFile, dstFile);
		
		
		/*
		String content = "i like like like java do you like a java";
		byte[] contentBytes = content.getBytes();//将string中的每个字符转换为对应的二进制码
		System.out.println("压缩前字节数" + contentBytes.length);
		byte[] huffmanCodeBytes = huffmanZip(contentBytes);
		System.out.println(Arrays.toString(huffmanCodeBytes));
		System.out.println("压缩后字节数" + huffmanCodeBytes.length);
		
		byte[] sourceBytes =  deCode(huffmanCodes, huffmanCodeBytes);
		//使用的String的toString方法
		System.out.println("原来的字符串" + new String(sourceBytes));
		*/
		
		
		/*
		//System.out.println(content.length());
		//System.out.println(Byte.toString(contentBytes[4]));
		//得到node的集合
		List<Node> nodes = getNodes(contentBytes);
		//System.out.println(nodes);
		//将nodes转化为哈夫曼树
		Node huffmanTreeRoot = createHuffmanTree(nodes);
		//preOrder(huffmanTreeRoot);
		
		//测试哈夫曼编码
		//getCodes(huffmanTreeRoot, "", stringBuilder);
		Map<Byte, String> huff = getCodes(huffmanTreeRoot);
		//System.out.println(huff);
		
		byte[] huffmanCodeBytes = zip(contentBytes, huff);
		System.out.println(Arrays.toString(huffmanCodeBytes));
		System.out.println(huffmanCodeBytes.length);//压缩为17个字节
		*/
		
	}

	
	//将文件解压
	/**
	 * 
	 * @param zipFile 准备解压的文件
	 * @param dstFile 解压的路径
	 */
	public static void unZipFile(String zipFile, String dstFile) {
		//定义文件输入流
		InputStream is = null;
		//定义对象的输入流
		ObjectInputStream ois = null;
		//定义文件的输出流
		OutputStream os = null;
		try {
			//创建文件输入流
			is = new FileInputStream(zipFile);
			//创建一个和is关联的对象输入流
			ois = new ObjectInputStream(is);
			//读取byte数组和huffmanBytes
			byte[] huffmanBytes = (byte[])ois.readObject();
			//读取哈夫曼编码表
			Map<Byte, String> huffmanCodes = (Map<Byte, String>)ois.readObject();
			//解码
			byte[] bytes = deCode(huffmanCodes, huffmanBytes);
			//将bytes数组写入到目标文件
			os = new FileOutputStream(dstFile);
			//写文件到dstFile文件
			os.write(bytes);
		} catch (Exception e) {
			// TODO: handle exception
			System.out.println(e.getMessage());
		} finally {
			try {
				os.close();
				ois.close();
				is.close();
			} catch (Exception e2) {
				// TODO: handle exception
				System.out.println(e2.getMessage());
			}
		}
	}
	
	
	
	
	//将文件进行压缩
	/**
	 * 
	 * @param srcFile 压缩文件的全路径
	 * @param dstFile 压缩后文件存放的目录
	 * @throws FileNotFoundException 
	 */
	public static void zipFile(String srcFile, String dstFile) {
		//创建输出流
		OutputStream os = null;
		ObjectOutputStream oos = null;
		//创建输入流
		FileInputStream is = null;
		try {
			is = new FileInputStream(srcFile);
			//创建一个和源文件一样大小的byte[]
			byte[] b = new byte[is.available()];
			//读取文件
			is.read(b);
			//对原文件压缩
			byte[] huffmanBytes = huffmanZip(b);
			//创建文件的输出流，存放压缩文件
			os = new FileOutputStream(dstFile);
			//创建一个和文件输出流相关联的ObjectOutputStream
			oos = new ObjectOutputStream(os);
			//这里以对象流的方式写入哈夫曼编码，是为了恢复源文件使用
			oos.writeObject(huffmanBytes);
			//把哈夫曼编码写入压缩文件
			oos.writeObject(huffmanCodes);
			
		} catch (Exception e) {
			// TODO: handle exception
			System.out.println(e.getMessage());
		} finally {
			try {
				is.close();
			} catch (Exception e2) {
				// TODO: handle exception
				System.out.println(e2.getMessage());
			}
		}
		
		
	}
	
	//数据的解压
	/*
	 * 1.将huffmanCode [-88, -65, -56, -65, -56, -65, -55, 77, -57, 6, -24, -14, -117, -4, -60, -90, 28]
	 * 转为对应的二进制10101000......
	 * 2. 二进制再转为字符串
	 * "i like like like java do you like a java"
	 * 
	 */
	/**
	 * 
	 * @param huffmanCodes 哈夫曼编码表
	 * @param huffmanBytes 哈夫曼编码得到的字节数组
	 * @return 原来字符串对应的二进制数组
	 */
	public static byte[] deCode(Map<Byte, String> huffmanCodes, byte[] huffmanBytes) {
		//先得到hunffmanButes对应的二进制字符串
		StringBuilder stringBuffer = new StringBuilder();
		//将byte[]转成字符串
		for (int i = 0; i < huffmanBytes.length; i++) {
			//判断是否是最后一个字节（因为其可能不为八位)
			boolean flag = (i == huffmanBytes.length - 1);
			stringBuffer.append(byteBitString(!flag, huffmanBytes[i]));
		}
		//把字符串按照哈夫曼编码解码
		//把K，V的值调换，方便查找
		HashMap<String, Byte> map = new HashMap<>();
		for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
			map.put(entry.getValue(), entry.getKey());
		}
		//创建集合，存放byte
		List<Byte> list = new ArrayList<>();
		//扫描stringBuilder
		for (int i = 0; i < stringBuilder.length();) {
			int count = 1;//计数器
			boolean flag = true;
			Byte b = null;
			while (flag) {
				//递增取出
				//i不懂，count不断向后移动，直到匹配到一个字符
				String key = stringBuilder.substring(i, i + count);
				b = map.get(key);//匹配到返回V，没有返回null
				if (b == null) {
					count++;//继续进行下一轮匹配
				} else {
					flag = false;//匹配到退出
				}
			}
			list.add(b);
			i += count;//i移动到未匹配的位置
		}
		//循环结束后，list中就存放了"i like like like java do you like a java"
		//将其挨个放入byte
		byte[] b = new byte[list.size()];
		for (int i = 0; i < b.length; i++) {
			b[i] = list.get(i);
		}
		return b;
	}
	
	
	
	
	
	
	/**
	 * 将一个byte转成一个二进制的字符串
	 * @param b
	 * @param flag 标志是否需要补高位，前面的byte[]是八个分一组，最后一组可能不够八个，但也分成了一组，所以需要判断
	 * @return 返回对应的二进制字符串（补码）
	 */
	public static String byteBitString(boolean flag, byte b) {
		//使用变量保存b
		int temp = (int)b;//将b转成int，为了使用方法
		//int类型32位,如果该数为负数，自然满足八位，如果为正数，例如1，对应的二进制就是1，不满足八位
		//正数需要补高位
		if (flag) {
			temp |= 256;//256的二进制补码为1 0000 0000 | 0000 0001 == 1 0000 00001
			//这样处理过后，1就能够取到八位
		}
		String str = Integer.toBinaryString(temp);//返回的是对应的二进制补码
		//但我们原本的数据为byte,所以取8位
		if (flag) {//需要取8位的[24,32)
			return str.substring(str.length() - 8);
		} else {//不足八位的（例如1），直接返回
			return str;
		}
	}
	
	
	
	
	
	//将所有的语句封装，便于调用
	/**
	 * 
	 * @param bytes 原始字符串对应的字节数组（二进制数组）
	 * @return 经过哈夫曼编码处理过后的字节数组《即压缩数组》
	 */
	public static byte[] huffmanZip(byte[] bytes) {
		List<Node> nodes = getNodes(bytes);
		//根据node创建哈夫曼树
		Node huffmanTreeRoot = createHuffmanTree(nodes);
		//对应的哈夫曼编码
		Map<Byte, String> huffmanCodes = getCodes(huffmanTreeRoot);
		//根据生成的哈夫曼编码压缩，得到对应的编码数组
		byte[] huffmanCodeBytes = zip(bytes, huffmanCodes);
		return huffmanCodeBytes;
	}
	
	
	//编写一个方法，将字符串对应的byte[]数组，通过哈夫曼编码表，返回一个哈夫曼编码压缩后的byte[]
	/**
	 * 
	 * @param bytes 原始字符串对应的byte[]
	 * @param huffmanCodes 生成的哈夫曼编码
	 * @return 返回处理过后的byte[]
	 * 空格=01 a=100 d=11000 u=11001 e=1110 v=11011 i=101 y=11010 j=0010 k=1111 l=000 o=0011
	 * 编码为： 1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100
	 * 我们八个一组，因为若不是这样，每个byte都是一个字节大小，（例如，空格为01，但仍要占据一个字节，就会自动补成8位，相当于没压缩，所以不如和后面的一起拼接为8位）
	 * 但需注意存储的都是补码，10101000补码，10100111反码，11011000原码  十进制-88
	 */
	public static byte[] zip(byte[] bytes, Map<Byte, String> huffmanCodes) {
		//利用huffmanCode将bytes转成哈夫曼编码对应的字符串
		//遍历bytes数组
		for (byte b : bytes) {
			stringBuilder.append(huffmanCodes.get(b));
		}
		//统计返回byte[]huffmanCodeBytes长度
		//也就是stringBuilder8个一组能够分成几段，不足8的也按照1段
		int len = 0;
		if (stringBuilder.length() % 8 == 0) {
			len = stringBuilder.length() / 8;
		} else {
			len = stringBuilder.length() / 8 + 1;
		}
		//或者这样写
		//int len = (stringBuilder.length() + 7) / 8;
		//创建huffmanCodeBytes
		byte[] huffmanCodeBytes = new byte[len];
		int index = 0;//记录是第几个byte
		for (int i = 0; i < stringBuilder.length(); i += 8) {//8位一组，所以步长+8
			String strByte;
			if (i + 8 > stringBuilder.length()) {//最后位数不够八位
				strByte = stringBuilder.substring(i);
			} else {
				strByte = stringBuilder.substring(i, i + 8);
			}
			//将strByte转成byte，放到huffmanCodeBytes
			huffmanCodeBytes[index] = (byte)Integer.parseInt(strByte, 2);
			index++;
		}
		return huffmanCodeBytes;
	}
	
	
	
	
	
	
	//将哈夫曼编码放到Map<Byte,  String>
	//定义Stringbuilder存储路径（方便拼接）
	static Map<Byte, String> huffmanCodes = new HashMap<>();
	static StringBuilder stringBuilder = new StringBuilder();
	
	//重载
	public static Map<Byte, String> getCodes(Node root) {
		if (root == null) {
			return null;
		}
		//处理root的左树
//		getCodes(root.left, "0", stringBuilder);
//		//处理root的右树
//		getCodes(root.right, "1", stringBuilder);
		getCodes(root, "", stringBuilder);
		return huffmanCodes;
	}
	
	/**
	 * 将传入的node结点的所有叶子节点的哈夫曼编码得到，并放入huffmanCodes集合
	 * @param node 传入结点
	 * @param code 路径 左子节点是0， 右子节点是1
	 * @param stringBuilder 用于拼接路径
	 */
	public static void getCodes(Node node, String code, StringBuilder stringBuilder) {
		StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
		//将code加入到stringBuilder2
		stringBuilder2.append(code);
		if (node != null) {
			//判断当前node是叶子节点还是非叶子结点
			if (node.data == null) {//非叶子节点
				//递归处理
				//向左
				getCodes(node.left, "0", stringBuilder2);
				//向右
				getCodes(node.right, "1", stringBuilder2);
			} else {//说明是叶子结点
				//将其添加到huffmanCodes
				huffmanCodes.put(node.data, stringBuilder2.toString());
			}
		}
	}
	
	public static void preOrder(Node root) {
		if (root != null) {
			root.preOrder();
		} else {
			System.out.println("空树！");
		}
	}
	/**
	 * 
	 * @param bytes 字节数组
	 * @return 返回的是List<Node>
	 */
	public static List<Node> getNodes(byte[] bytes) {
		//创建一个ArrayList，存放Node
		List<Node> nodes = new ArrayList<>();
		//遍历bytes，统计各个字符出现的次数
		Map<Byte, Integer> counts = new HashMap<>();
		for (byte b : bytes) {
			Integer count = counts.get(b);//通过K，找到对应的V，没有则为null
			if (count == null) {
				counts.put(b, 1);//没有就放进去，个数为1
			} else {
				counts.put(b, count + 1);//有，就+1
			}
		}
		//把每一个<k,v>转换成一个Node对象，加入到nodes集合
		//遍历counts
		//Set<Map.Entry<Byte,Integer>> entrySet = counts.entrySet();
		for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
			nodes.add(new Node(entry.getKey(), entry.getValue()));
		}
		return nodes;
	}
	
	//通过List创建对应的哈夫曼树
	public static Node createHuffmanTree(List<Node> nodes) {
		while (nodes.size() > 1) {
			//Node重写了comparaTo方法
			Collections.sort(nodes);
			Node leftNode = nodes.get(0);
			Node rightNode = nodes.get(1);
			Node parent = new Node(null, leftNode.weight + rightNode.weight);
			parent.left = leftNode;
			parent.right = rightNode;
			nodes.remove(leftNode);
			nodes.remove(rightNode);
			nodes.add(parent);
		}
		return nodes.get(0);
	}
}

//创建Node，
class Node implements Comparable<Node>{
	Byte data;//存放字符，'a'==97
	int weight;//权值
	Node left;
	Node right;
	
	public Node(Byte data, int weight) {
		super();
		this.data = data;
		this.weight = weight;
	}

	@Override
	public int compareTo(Node o) {
		//从小到大
		return this.weight - o.weight;
	}

	@Override
	public String toString() {
		return "Node [data=" + data + ", weight=" + weight + "]";
	}
	
	public void preOrder() {
		System.out.println(this);
		if (this.left != null) {
			this.left.preOrder();
		}
		if (this.right != null) {
			this.right.preOrder();
		}
	}
	
}